package hzk.codex2016.sort;

public class InsertionSorter implements Sorter {
	public void sort(int[] a) {
		int tmp, i, j, n = a.length;
		for (i = 1; i < n; ++i) { // insert a[i] to a[0..i-1]
			for (j = i; j > 0 && a[j] < a[j - 1]; --j) {
				tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
			}

		}
	}

	// a bit optimized
	public void sort2(int[] a) {
		int tmp, i, j, n = a.length;
		for (i = 1; i < n; ++i) { // insert a[i] to a[0..i-1]
			tmp = a[i];
			for (j = i - 1; j >= 0 && tmp < a[j]; --j) {
				a[j + 1] = a[j];
			}
			a[j + 1] = tmp;

		}
	}

	public static void main(String[] args) {
		Sorter s = new InsertionSorter();
		for (int i = 1; i < 10; i++) {
			Arrs.test(s, i);
		}
		for (int i = 100; i < 1e5; i *= 10) {
			Arrs.test(s, i);
		}
		for (int i = 1; i <= 3; i++) {
			Arrs.test(s, 110000);
		}
	}

}
